2214. Function 9

Write a program that finds the value of the function

f(m, n) =

Input. Two positive integers n and m (1 ≤ n, m ≤ 10¹⁸).

Output. Print the value of the function f(m, n).

Sample input	Sample output
6 3	3

SOLUTION

recursion

Algorithm analysis

The function f(m, n) calculates the greatest common divisor (GCD) of numbers m and n. To solve the problem, it is enough to implement the GCD of two numbers using the operation of taking the modulus instead of subtracting.

Algorithm realization

Function gcd returns the greater common divisor of numbers a and b.

long long gcd(long long a, long long b)

{

return (!b) ? a : gcd(b, a % b);

}

The main part of the program. Read input values n and m in the order given in the problem statement (first n and then m).

scanf("%lld %lld", &n, &m);

Calculate and print the value of f(m, n).

res = gcd(m, n);

printf("%lld\n", res);